\documentclass[12pt, titlepage]{article}

\usepackage[UTF8]{ctex}
\usepackage{url}
\usepackage[hidelinks]{hyperref}
\usepackage{listings}
\usepackage{booktabs, siunitx}
\usepackage{makecell}
\usepackage{bm}
\usepackage{halloweenmath}
\usepackage{graphicx}
\usepackage{fancyhdr}
\newcommand{\tabincell}[2]{\begin{tabular}{@{}#1@{}}#2\end{tabular}}


\author{eleve11}
\title{优化的基本原则}
\pagestyle{fancy}

\begin{document}
\maketitle

\newpage
\section{介绍}
非线性规划基于定义，定理和原理的集合，如果要有效地使用可用的非线性编程方法，必须清楚地理解这些定义，定理和原理。
\begin{displaymath}
minimize \quad f = f(x) \quad s.t. \qquad x \in \Re
\end{displaymath}
上式是一个实值函数，其中$\Re$为可行域。

\section{梯度信息}
在许多优化方法中，需要与目标函数有关的梯度信息。该信息由关于n个变量的f（x）的一阶和二阶导数组成。 \\
\indent 若果$f(\bm{x})$存在连续的一阶偏导即$f(\bm{x})$的Gradient：
\begin{displaymath}
  g(\bm{x}) = [\frac{\partial f}{\partial x_1} \quad \frac{\partial f}{\partial x_2} \quad \ldots \quad \frac{\partial f}{\partial x_n}]^T = \nabla f(\bm{x})
\end{displaymath}
\indent 若果$f(\bm{x})$存在连续的二阶偏导即$f(\bm{x})$的Hessian：
\begin{displaymath}
  H(\bm{x}) = \nabla g^T = \nabla {\nabla ^T f(\bm{x})}
\end{displaymath}
\begin{displaymath}
  H(\bm{x}) = \begin{bmatrix}
    \frac{\partial ^2 f}{\partial x_1^2} & \frac{\partial ^2 f}{\partial x_1 x_2} & \cdots & \frac{\partial ^2 f}{\partial x_1 x_n} \\
    \frac{\partial ^2 f}{\partial x_2 x_1} & \frac{\partial ^2 f}{\partial x_2^2} & \cdots & \frac{\partial ^2 f}{\partial x_2 x_n} \\
    \vdots & \vdots & \ddots & \vdots \\
    \frac{\partial ^2 f}{\partial x_n x_1} & \frac{\partial ^2 f}{\partial x_n x_2} & \cdots & \frac{\partial ^2 f}{\partial x_n^2}
  \end{bmatrix}
\end{displaymath}
因为$\frac{\partial ^2 f}{\partial x_i x_j} = \frac{\partial ^2 f}{\partial x_j x_i}$，所以Hessian是对称矩阵。Gradient和Hessian是用于简化优化过程，但是在某些确定的应用中可能会不经济、会耗时，也可能无法推断和计算$f(\bm{x})$的偏导数，遇到这样的应用应该抛弃使用梯度信息的方法。

\section{泰勒级数}
高等数学中学到过泰勒中值定理：
\newtheorem{thm}{定理}
\begin{thm}[泰勒中值定理]
    如果函数$f(x)$在$x_0$处具有n阶导数，那么存在$x_0$的一个邻域，对于该邻域内的任意$x$，有：$f(x) = f(x_0) + f^{'}(x_0)(x-x_0)+\frac{f^{''}(x_0)}{2!}(x-x_0)^2+\ldots+\frac{f^{(n)}(x_0)}{n!}(x-x_0)^n+R_n(x)$，其中$R_n(x) = o((x-x_0)^n)$
\end{thm}
\begin{thm}[二元函数泰勒定理]
    如果函数$f(x, y)$在$(x_0, y_0)$内连续且具有$n+1$阶连续偏导数，$(x_0+h, y_0+k)$邻域内任意一点，则有：
    $f(x_0+h, y_0+k) = f(x_0, y_0)+(h \frac{\partial}{\partial x}+k \frac{\partial}{\partial y})f(x_0, y_0)+\frac{1}{2!}(h \frac{\partial}{\partial x}+k \frac{\partial}{\partial y})^2f(x_0, y_0)+\ldots+\frac{1}{(n+1)!}(h \frac{\partial}{\partial x}+k \frac{\partial}{\partial y})^{n+1}f(x_0+ \theta h, y_0+ \theta k)$
\end{thm}
处理一些非线性优化的过程和方法会利用线性或二次逼近的目标函数及其等式与不等式约束，我们可以通过泰勒级数逼近得到。

\section{极值的类型}
一个函数的极值可分为极大值与极小值，极值也分为全局极值与局部极值。
\begin{enumerate}
  \item \textbf{弱局部最小值}：在可行域$\Re$中存在一个距离使得可行点满足距离$\varepsilon < 0$，即：$f(x) \geq f(x^*) \quad \textrm{if} \quad x \in \Re \quad \textrm{and} \quad \| x-x^* \| < \varepsilon$
  \item \textbf{弱全局最小值}：对于所有属于可行域的点，有$f(x) \geq f(x^*)$，则$x^*$为全局最小值
  \item \textbf{强最值}：当上述1和2中去掉等号，我们就可得到强最值
\end{enumerate}
当然极大则将不等式翻转即可得到。

\section{局部最小值和最大值的必要和充分条件}
在局部最小点$x^*$，Gradient $g(x)$和Hessian H(x)必须满足一些确定的条件，这些条件分为两类：满足局部最小值$x^*$应该满足的一些必要条件，与保证$x^*$为局部最小值的充分条件。
\newtheorem{definition}{定义}
\begin{definition}
  $\bm{\delta} = \alpha \bm{x}$是关于向量$\bm{x}$的变化向量，其中$\alpha$为正常数，$\delta$是方向向量，如果满足在可行域$\Re$中，$\bm{x} + \alpha \bm{d} \in \Re$(其中任意$\alpha$满足$0<\alpha < \hat{\alpha}$)，$\bm{d}$为$\bm{x}$的可行方向向量。
\end{definition}
也就是说一个在可行域中的点$\bm{x}$，沿方向$\bm{d}$移动一个有限的距离，依旧在可行域中，则说$\bm{d}$为可行方向。 \\
\indent 此外，条件可以安装偏导数划分，一阶条件即依据一阶导数，二阶条件即依据一阶和二阶导数。
\subsection{一阶必要条件}
以下$f(x) \in C^p$，表示函数有p阶导。
\begin{thm}
  最小值的一阶必要条件 \\
  (a).如果$f(x) \in C^1$，并且$x^*$是一个局部最小值，然后对于点$\bm{x}^*$所有的可行方向$\bm{d}$有$g(\bm{x}^*)^T \bm{d} \geq 0$ \\
  (b).如果$\bm{x}^*$在可行域$\Re$的内部则有: $g(\bm{x}^*)^T = 0$
\end{thm}
\subsection{二阶必要条件}
\begin{definition}
  (a).设$\bm{d}$为点$\bm{x}$的任意方向向量，二次形式$\bm{d} ^T H(\bm{x}) \bm{d}$可能是正定，半正定，负定，半负定，如果其不能确定正负，则方向向量$\bm{d}$是不确定的。
  \\ (b).如果$\bm{d} ^T H(\bm{x}) \bm{d}$是正定或半正定，则$H(\bm{x})$亦是正定或半正定的
\end{definition}
\begin{thm}
  最小值的二阶必要条件 \\
  (a).如果$f(x)\in C^2$，且$\bm{x}^*$为局部最小值，则对于点$\bm{x}^*$所有可行方向向量$\bm{d}$有：(\romannumeral1).$g(\bm{x}^*)^T \bm{d} \geq 0$。 (\romannumeral2).如果$g(\bm{x}^*)^T \bm{d} = 0$，则$\bm{d}^T H(\bm{x}^*) \bm{d} \geq 0$ \\
  (b).如果点$\bm{x^*}$为可行域$\Re$内部的局部最小值，则有: (\romannumeral1). $g(\bm{x}^*)^T = 0$。 (\romannumeral2). 对于所有反向向量$\bm{d} \neq 0$，有$\bm{d}^T H(\bm{x}^*) \bm{d} \geq 0$
\end{thm}
\subsection{二阶充分条件}
\begin{thm}
  最小值的二阶充分条件，\\ 如果函数$f(x) \in C^2$并且$x^*$在可行域$\Re$的内部，满足条件(a).$g(\bm{x}^*)=0$，(b).$H(\bm{x}^*)$是正定的，则点$\bm{x}^*$是一个强局部最优值。
\end{thm}




\newpage
\begin{thebibliography}{99}
  \bibitem{b} Andreas A, Wu-Sheng L. Practical Optimization Algorithms and Engineering Applications (2007)
\end{thebibliography}

\end{document}
